package LeetCode;


//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//你不需要保留每个分区中各节点的初始相对位置。
public class TesrInterview02_04 {
    public ListNode partition(ListNode head, int x) {
        //判空
        if (head == null) {
            return null;
        }
        //定义大小头节点
        ListNode smallHead = new ListNode(101);
        ListNode smallTail = smallHead;
        ListNode bigHead = new ListNode(101);
        ListNode bigTail = bigHead;
        while (head != null) {
            if (head.val < x) {
                //将头节点插入到小节点下一节点
                smallTail.next = head;
                smallTail = head;
            } else {
                //将头节点插入到大节点下一节点
                bigTail.next = head;
                bigTail = head;
            }
            //完成一次比较，头节点指向下一节点
            head = head.next;
        }
        //将大节点的下一节点指空
        bigTail.next = null;
        //小节点连接大节点
        smallTail.next = bigHead.next;
        return smallHead.next;
    }
}
